package com.hanlin.day06;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 描述：
 * 测试链接：https://leetcode.com/problems/merge-k-sorted-lists/
 * @author:hl.yuan
 * @date:2022-07-16
 */
public class Code01_MergeKSortedLists {
    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode() {}
        public ListNode(int val) {
            this.val = val;
        }
    }

    public static class ListNodeComparator implements Comparator<ListNode> {

        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }

    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        // 定义个顺序队列
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
        // 循环的把所有的节点信息放进队列里
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.add(lists[i]);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        // 得到顺序队列里面的第一个值，也就是头节点
        ListNode head = heap.poll();
        ListNode pre = head;
        // 看看头结点下面是不是空的。如果不是空的，就添加到顺序队列里
        if (pre.next != null) {
            heap.add(pre.next);
        }
        while (!heap.isEmpty()) {
            // 在弹出一个最小的节点。
            ListNode cur = heap.poll();
            // 把头结点的下一个位置，设置上这个最小的节点。（这里的pre.next是设置的head的下一个节点）
            pre.next = cur;
            // 把当前对象引用地址改成cur。
            pre = cur;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(2);
        listNode1.next.next = new ListNode(3);
        ListNode listNode2 = new ListNode(3);
        listNode2.next = new ListNode(4);
        listNode2.next.next = new ListNode(5);

        ListNode[] listNodes = new ListNode[2];
        listNodes[0] = listNode1;
        listNodes[1] = listNode2;

        ListNode listNode = mergeKLists(listNodes);
        System.out.println(listNode);
    }
}
